//
// Created by Lantz on 2024/3/5.
//
#include <stdio.h>
#include <stdlib.h>

typedef int Elem;
typedef struct Node {
    Elem data;
    struct Node *next;
} LNode, *LinkList;

// 按序号查找
LinkList GetElem(LinkList L, int i) {
    int j = 0;
    LNode * p = L;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

// 按值查找
LinkList GetValue(LinkList L, Elem e) {
    LNode *p = L->next;
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

// 打印遍历
void printList(LinkList L) {
    LNode * p = L->next;
    while (p != NULL){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 头插法
LinkList HeadInsert(LinkList &L) {
    int x;
    L = (LNode *) malloc(sizeof(Node));
    LNode * s;
    L->next = NULL; // 初始化为空链表
    scanf("%d", &x);
    while (x != 9999){
        s = (LNode *) malloc(sizeof(Node));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

// 尾插法
LinkList TailInsert(LinkList &L) {
    int x;
    L = (LNode *) malloc(sizeof(Node)); // 分配空间
    LNode *s, *r = L;
    scanf("%d", &x);
    while (x != 9999){ // 终止条件
        s = (LNode *) malloc(sizeof(Node)); // 新节点分配空间
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL; // 尾节点的指针域要为空，否则会出现报错
    return L;
}

// 插入元素
bool InsertElem(LinkList &L, int i, Elem e) {
//    GetElem(L, i);
    int j = 0;
    LNode * p = L;
    while (p != NULL && j < i-1) {
        p = p->next;
        j++;
    }
//    LNode * p = L;
    if(p == NULL){
        return false;
    }
    LNode * s;
    s = (LinkList) malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 删除元素
bool DeleteElem(LinkList &L, int i, Elem &val) {
//    GetElem(L, i+1);
    int j = 0;
    LNode * p = L;
    while (p != NULL && j < i-1) {
        p = p->next;
        j++;
    }
//    LNode * p = L;
    if(p == NULL || p->next == NULL){
        return false;
    }
    LNode * q = p->next; // 指向要删除的节点
    val = q->data;
    p->next = q->next;
    free(q);
    q = NULL; // 避免野指针
    return true;
}

int main(void) {
    LinkList L;
    int pos = 2;
    Elem val;

    LinkList search;
    TailInsert(L);
    search = GetElem(L, 2);
    printf("%d\n", search->data);
    printList(L);
//    HeadInsert(L);
//    printList(L);
    InsertElem(L, pos, 99);
    printList(L);
    DeleteElem(L, pos, val);
    printf("The delete element is %d\n", val);
    printList(L);
    return 0;
}

// 3 4 5 6 7 8 9999